package main

import "go-leetcode/leetcode/utils"

// 235.回文链表
func main() {
	listNode := utils.GetListNodeByArray([]int{5, 6, 1, 1, 6, 5})
	has := isPalindrome(listNode)

	println(has)

	return
}

func isPalindrome2(head *utils.ListNode) bool {
	// 时间复杂度O(n)，空间复杂度 O(1)
	// 使用递归处理
	return true
}

func isPalindrome(head *utils.ListNode) bool {
	//辅助数组 时间复杂度O(n)，空间复杂度 O(n)
	var nodeNums []int

	pointHead := head

	for pointHead != nil {
		nodeNums = append(nodeNums, pointHead.Val)
		pointHead = pointHead.Next
	}

	n := len(nodeNums)
	for i := 0; i < n/2; i++ {
		if nodeNums[i] != nodeNums[n-1-i] {
			return false
		}
	}

	return true
}

// 给你一个单链表的头节点 head ，请你判断该链表是否为回文链表。如果是，返回 true ；否则，返回 false 。
//
//示例 1：
//
//输入：head = [1,2,2,1]
//输出：true
//示例 2：
//
//输入：head = [1,2]
//输出：false
//
//提示：
//
//链表中节点数目在范围[1, 105] 内
//0 <= Node.val <= 9
//
//进阶：你能否用 O(n) 时间复杂度和 O(1) 空间复杂度解决此题？
